package org.hhchat.leetcode.tree;

/**
 * Created by HMH on 2017/3/30.
 */

import org.hhchat.leetcode.dataStruct.TreeNode;

/**
 * 437.Path Sum III
 */
public class code437 {
    public static class Solution {

        int find=0;
        public int pathSum(TreeNode root, int sum) {
            if (root == null) {
                return find;
            }
            dfs(root, sum);
            pathSum(root.left, sum);
            pathSum(root.right, sum);
            return find;
        }

        private void dfs(TreeNode node,int sum) {
            if (node == null) {
                return;
            }
            if (sum==node.val) {
                find++;
            }
            dfs(node.left, sum-node.val);
            dfs(node.right, sum-node.val);

        }
    }
    public static void main(String[] args){
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.right = new TreeNode(-3);
        root.left.left=new TreeNode(3);
        root.left.right=new TreeNode(2);
        root.left.left.left=new TreeNode(3);
        root.left.left.right=new TreeNode(-2);
        root.left.right.right=new TreeNode(1);
        root.right.right = new TreeNode(11);
        System.out.println(new Solution().pathSum(root,8));
    }
}
